﻿// 0802train02.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <sstream>
#include <unordered_map>
#include <unordered_set>
#include <queue>
#include <stack>
#include <limits.h>
#include <cmath>

using namespace std;


/*
 给定一个非负整数，你至多可以交换一次数字中的任意两位。返回你能得到的最大值。

示例 1 :

输入: 2736
输出: 7236
解释: 交换数字2和数字7。
示例 2 :

输入: 9973
输出: 9973
解释: 不需要交换。
 */

int Swap01(string&num_str, int pos_1, int pos_2)
{
    string oh_str = num_str;
    char tmp = oh_str[pos_1];
    oh_str[pos_1] = oh_str[pos_2];
    oh_str[pos_2] = tmp;

    return stoi(oh_str);
    //Swap01
}

int Solve01(int num) {

    string num_str = to_string(num);
    int str_size = num_str.size();

    int result = num;
    for (int i=0; i<str_size; i++)
    {
        for (int j=i+1; j<str_size; j++)
        {
            int swap_num = Swap01(num_str, i, j);
            result = max(result, swap_num);
        }

        //for------
    }

    return result;
    //maximumSwap
}


int Solve11(int num)
{
    string num_str = to_string(num);
    int str_size = num_str.size();

    int max_id = str_size -1, swap_1 = -1, swap_2 = -1;

    for (int i=str_size-1; i>=0; i--)
    {
        char curr_char = num_str[i];

        if (curr_char>num_str[max_id])
        {
            max_id = i;
        }
        else if (curr_char<num_str[max_id])
        {
            swap_1 = i;
            swap_2 = max_id;
        }
        //for------
    }
    if (swap_1>=0)
    {
        return Swap01(num_str, swap_1, swap_2);
    }
    return num;
    //solve11
    //------
}



/*
 给定一个字符串s，最多只能进行一次变换，返回变换后能得到的最小字符串（按照字典序进行比较）
变换规则： 交换字符串中任意两个不同位置的字符。

输入描述
一串小写字母组成的字符串s

输出描述
按照要求进行变换得到的最小字符串

补充说明
s是都是小写字符组成
1 <= s.length <= 1000


输入
edcba

输出
adcbe
 */

string Swap02(string oh_str, int index_1, int index_2)
{
    char tmp = oh_str[index_1];
    oh_str[index_1] = oh_str[index_2];
    oh_str[index_2] = tmp;

    return oh_str;
	//Swap02------
}

void solve02(string oh_str)
{
    string result = oh_str;
    for (int i=0; i<oh_str.size();i++)
    {
	    for (int j=i+1; j<oh_str.size();j++)
	    {
            string new_str = Swap02(oh_str, i, j);
            result = min(result, new_str);
	    }
    }

    cout << result;
    //solve02------
}

void solve021(string oh_str)
{
    int str_size = oh_str.size();
    int min_id = str_size - 1, swap_1 = -1, swap_2 = -1;

    for (int i=str_size-1; i>=0; i--)
    {
        char curr_char = oh_str[i];
        if (curr_char<oh_str[min_id])
        {
            min_id = i;
        }
        if (curr_char>oh_str[min_id])
        {
            swap_1 = i;
            swap_2 = min_id;
        }

        //for------
    }

    string result = oh_str;
    if (swap_1>=0)
    {
        result = Swap02(oh_str, swap_1, swap_2);
    }
    cout << result;
    //solve021
}



/*
 people[i]表示第 i 个人的体重 ，船的数量不限，每艘船可以承载的最大重量为 limit。
每艘船最多可同时载两人，但条件是这些人的重量之和最多为 limit。
返回 承载所有人所需的最小船数 。 
示例 1：
输入：people = [1,2], limit = 3
输出：1
解释：1 艘船载 (1, 2)
示例 2：
输入：people = [3,2,2,1], limit = 3
输出：3
解释：3 艘船分别载 (1, 2), (2) 和 (3)
示例 3：
输入：people = [3,5,3,4], limit = 5
输出：4
解释：4 艘船分别载 (3), (3), (4), (5)
 */

void solve03(vector<int>&oh_vec, int limit)
{
    sort(oh_vec.begin(), oh_vec.end());

    int result = 0;

    unordered_set<int>index_set;

    for (int i=0;i<oh_vec.size();i++)
    {
        if (index_set.count(i)) continue;

        int curr_num = oh_vec[i];
        int remain_weight = limit - curr_num;
        int target_index = -1;
        for (int j= oh_vec.size()-1; j>=i+1; j--)
        {
	        if (oh_vec[j] <= remain_weight && !index_set.count(j))
	        {
                target_index = j;
                break;
	        }
        }

        if (target_index>=0)
        {
            index_set.insert(target_index);
            index_set.insert(i);
            result += 1;
        }
        else
        {
            index_set.insert(i);
            result += 1;
        }

        //for------
    }
    cout << result;
    //solve03
    //------
}



void solve131(vector<int>& oh_vec, int limit)
{
    sort(oh_vec.begin(), oh_vec.end());

    int vec_size = oh_vec.size();
    int left = 0;
    int right = vec_size - 1;
    int result = 0;

    while (left<=right)
    {
        if (left==right&&oh_vec[left]<=limit)
        {
            result += 1;
            break;
        }

        if (oh_vec[left]+oh_vec[right]<=limit)
        {
            result += 1;
            left += 1;
            right -= 1;
        }
        else
        {
            result += 1;
            right -= 1;
        }
        //while
    }
    cout << result;
    //solve131
}

int main()
{
	{
        //people = [3,2,2,1], limit = 3 3
        //people = [3, 5, 3, 4], limit = 5 4
        //people = [5,1,4,2], limit=6 2
        vector<int>people = { 5,1,4,2 };
        int limit = 6;
        solve131(people, limit);

        return 0;
	}

	{
        string oh_str;
        cin >> oh_str;

        solve021(oh_str);
        return 0;
	}

    cout << Solve11(2736);
    //cout << maximumSwap(2736);
    //cout << Swap01(oh_str, 0, 3) << endl;
    //cout << oh_str << endl;
}

// 运行程序: Ctrl + F5 或调试 >“开始执行(不调试)”菜单
// 调试程序: F5 或调试 >“开始调试”菜单

// 入门使用技巧: 
//   1. 使用解决方案资源管理器窗口添加/管理文件
//   2. 使用团队资源管理器窗口连接到源代码管理
//   3. 使用输出窗口查看生成输出和其他消息
//   4. 使用错误列表窗口查看错误
//   5. 转到“项目”>“添加新项”以创建新的代码文件，或转到“项目”>“添加现有项”以将现有代码文件添加到项目
//   6. 将来，若要再次打开此项目，请转到“文件”>“打开”>“项目”并选择 .sln 文件
